{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Subsequence in Non-Increasing Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #非递增顺序的最小子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>nums</code>，请你从中抽取一个子序列，满足该子序列的元素之和 <strong>严格</strong> 大于未包含在该子序列中的各元素之和。</p>\n",
    "\n",
    "<p>如果存在多个解决方案，只需返回 <strong>长度最小</strong> 的子序列。如果仍然有多个解决方案，则返回 <strong>元素之和最大</strong> 的子序列。</p>\n",
    "\n",
    "<p>与子数组不同的地方在于，「数组的子序列」不强调元素在原数组中的连续性，也就是说，它可以通过从数组中分离一些（也可能不分离）元素得到。</p>\n",
    "\n",
    "<p><strong>注意</strong>，题目数据保证满足所有约束条件的解决方案是 <strong>唯一</strong> 的。同时，返回的答案应当按 <strong>非递增顺序</strong> 排列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4,3,10,9,8]\n",
    "<strong>输出：</strong>[10,9] \n",
    "<strong>解释：</strong>子序列 [10,9] 和 [10,8] 是最小的、满足元素之和大于其他各元素之和的子序列。但是 [10,9] 的元素之和最大。&nbsp;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4,4,7,6,7]\n",
    "<strong>输出：</strong>[7,7,6] \n",
    "<strong>解释：</strong>子序列 [7,7] 的和为 14 ，不严格大于剩下的其他元素之和（14 = 4 + 4 + 6）。因此，[7,6,7] 是满足题意的最小子序列。注意，元素按非递增顺序返回。  \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [6]\n",
    "<strong>输出：</strong>[6]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 500</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-subsequence-in-non-increasing-order](https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-subsequence-in-non-increasing-order](https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,10,9,8]', '[4,4,7,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        lsum = []\n",
    "        rsum = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if sum(lsum)<=rsum:\n",
    "                lsum.append(nums[i])\n",
    "                rsum -= nums[i]\n",
    "        return lsum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        sum_now = sum(nums)\n",
    "        sum1 = 0\n",
    "        for i in range(0,len(nums)):\n",
    "            sum1+=nums[i]\n",
    "            sum_now -= nums[i]\n",
    "            if sum1>sum_now:\n",
    "                return nums[0:i+1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums):\n",
    "        nums.sort(reverse=True)\n",
    "        for i in range(len(nums)):\n",
    "            if i < len(nums) - 1 and sum(nums[:i+1:]) > sum(nums[i+1::]):\n",
    "                return nums[:i + 1:]\n",
    "        \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        n = sum(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        res,tmp = [],0\n",
    "        for i in nums:\n",
    "            res.append(i)\n",
    "            tmp += i\n",
    "            if tmp > n-tmp:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        num=sorted(nums)\n",
    "        sums=0\n",
    "        \n",
    "        result=[]\n",
    "        for i in range(len(num)-1,-1,-1):\n",
    "            sums=sums+num[i]\n",
    "            result.append(num[i])\n",
    "            s=0\n",
    "            for n in range(i):\n",
    "                s+=num[n]\n",
    "            if sums>s:\n",
    "                return result\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        # 先排序\n",
    "        nums.sort(reverse = True)\n",
    "        sum = 0\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "        # 获得总数\n",
    "        res = []\n",
    "        count = 0\n",
    "        for i in nums:\n",
    "            count += i\n",
    "            res.append(i)\n",
    "            if count > sum // 2:\n",
    "                return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        he = sum(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        ls = []\n",
    "        s = 0\n",
    "        for i in nums:\n",
    "            s += i\n",
    "            ls.append(i)\n",
    "            if s > he - s:\n",
    "                return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        s = sum(nums)\n",
    "        total = 0\n",
    "        for n in reversed(nums):\n",
    "            total += n\n",
    "            ans.append(n)\n",
    "            if total > s - total:\n",
    "                break\n",
    "        \n",
    "        ans.sort(reverse=True)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot,s = sum(nums),0\n",
    "        for i,num in enumerate(nums):\n",
    "            s += num\n",
    "            if s>tot-s:return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot,s=sum(nums),0\n",
    "        for i ,num in enumerate(nums):\n",
    "            s+=num\n",
    "            if s>tot-s:\n",
    "                return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        s = sum(nums)\n",
    "        t = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            t += v\n",
    "            if t > s - t:\n",
    "                return nums[:i + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        sum_all = sum(nums)\n",
    "        res = []\n",
    "        sum_ = 0\n",
    "        for num in nums:\n",
    "            sum_ += num\n",
    "            res.append(num)\n",
    "            if sum_ > (sum_all-sum_):\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        n = sum(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        res,tmp = [],0\n",
    "        for i in nums:\n",
    "            res.append(i)\n",
    "            tmp += i\n",
    "            if tmp > n-tmp:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        t = sum(nums)//2\n",
    "        nums.sort(reverse = True);e = nums[0]\n",
    "        for i in range(len(nums)-1):\n",
    "            if e > t:\n",
    "                return nums[:i+1]\n",
    "            e = e + nums[i+1]\n",
    "        return nums\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        sum1=sum(nums)\n",
    "        sum2=0\n",
    "        heap=[-num for num in nums]\n",
    "        heapq.heapify(heap) \n",
    "        while(sum2<=sum1):\n",
    "            poped=(heapq.heappop(heap))*-1\n",
    "            res.append(poped)\n",
    "            sum2+=poped\n",
    "            sum1-=poped\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        if len(nums) == 1:\n",
    "            return nums\n",
    "        res = []\n",
    "        for i in range(0, len(nums)):\n",
    "            res.append(nums[i])\n",
    "            if sum(res) > sum(nums[i+1:]):\n",
    "                return res\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        x=[i for i in nums]\n",
    "        x.sort(reverse=True)\n",
    "        res=[]\n",
    "        for i in x:\n",
    "            res.append(i)\n",
    "            if  sum(res)>sum(x)-sum(res):\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        n=sorted(nums,reverse=True)\n",
    "        s=sum(nums)\n",
    "        t=0\n",
    "        for i,j in enumerate(n):\n",
    "            t+=j\n",
    "            if t>s-t:\n",
    "                return n[:i+1]\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot, s = sum(nums), 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            if s > tot - s:\n",
    "                return nums[:i + 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        if len(nums)==1:\n",
    "            return nums\n",
    "        for i in range(1,len(nums)+1):\n",
    "            sum_max = 0\n",
    "            sum_min = 0\n",
    "            for j in nums[-i:]:\n",
    "                sum_max += j\n",
    "            for k in nums[:-i]:\n",
    "                sum_min += k\n",
    "            if sum_max > sum_min:\n",
    "                return nums[-i:][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        sum1=sum(nums)\n",
    "        sum2=0\n",
    "        nums.sort()\n",
    "        while(sum2<=sum1):\n",
    "            res.append(nums[-1])\n",
    "            \n",
    "            sum2+=nums[-1]\n",
    "            sum1-=nums[-1]\n",
    "            nums.pop(-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        sums = sum(nums)/2\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        s=0\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            s+=nums[i]\n",
    "            res.append(nums[i])\n",
    "            if s>sums:\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            if sum(ans) <= sum(nums)/2:\n",
    "                ans.append(n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        # s=sum(nums)\n",
    "        # nums.sort(reverse=True)\n",
    "        # ans=[]\n",
    "        # t=0\n",
    "        # for num in nums:\n",
    "        #     if t<=s-t:\n",
    "        #         t+=num\n",
    "        #         ans.append(num)\n",
    "        #     else:\n",
    "        #         break\n",
    "        # return ans\n",
    "\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        while sum(ans) <= sum(nums):\n",
    "            ans.append(nums[-1])\n",
    "            nums.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        while sum(ans) <= sum(nums):\n",
    "            ans.append(nums[-1])\n",
    "            nums.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums)==1 : return [nums[0]]\n",
    "        nums.sort(reverse=True)\n",
    "        j = len(nums) - 1\n",
    "        i = 0\n",
    "        sum_left = nums[0]\n",
    "        sum_right = nums[j]\n",
    "        left= [nums[i]]\n",
    "        right = [nums[j]]\n",
    "        if left==right:return right+left\n",
    "        while(i<j and i!=j-1):\n",
    "            if sum_left<=sum_right+nums[j-1]:\n",
    "                i += 1\n",
    "                sum_left+=nums[i]\n",
    "                left.append(nums[i])\n",
    "            if i==j-1:break\n",
    "            else:\n",
    "                j-=1\n",
    "                sum_right+=nums[j]\n",
    "                right.append(nums[j])\n",
    "                if i == j - 1: break\n",
    "        #print(sum_left,sum_right)\n",
    "        right.reverse()\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        a , res = sum(nums) , 0\n",
    "        for i , j in enumerate(nums):\n",
    "            res += j\n",
    "            if res > a - res:\n",
    "                return nums[: i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        s=sum(nums)\n",
    "        a=[]\n",
    "        t=0\n",
    "        for num in nums:\n",
    "            t+=num\n",
    "            a.append(num)\n",
    "            if t > s-t:\n",
    "                return a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot,s = sum(nums),0\n",
    "        for i,num in enumerate(nums):\n",
    "            s += num\n",
    "            if s > tot -s:\n",
    "                return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        # 排序 -> 前缀和\n",
    "        nums = sorted(nums ,reverse=True)\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0]*(n+1)\n",
    "        prefix_sum[0] = nums[0]\n",
    "        for i in range(1,n) :\n",
    "            prefix_sum[i] = prefix_sum[i-1] + nums[i] \n",
    "        for i in range(n) :\n",
    "            if prefix_sum[i] > (prefix_sum[n-1]-prefix_sum[i]) :\n",
    "                return nums[:i+1]\n",
    "        return nums # impossible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        maxx=sum(nums)\n",
    "        count=0\n",
    "        res=[]\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            count+=nums[i]\n",
    "            res.append(nums[i])\n",
    "            if count>maxx//2:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums2=sorted(nums)\n",
    "        result=[nums2[-1]]\n",
    "        if nums2[-1]>(sum(nums2)-nums2[-1]):\n",
    "                return result\n",
    "        for i in range(len(nums2)-2,-1,-1):\n",
    "            result.append(nums2[i])            \n",
    "            if sum(result)>(sum(nums2)-sum(result)):\n",
    "                return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        all_sums=sum(nums)\n",
    "        s=0\n",
    "        for i in range(len(nums)):\n",
    "            s+=nums[i]\n",
    "            if s*2>all_sums:\n",
    "                return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        #print(presum)\n",
    "        return nums[:bisect_left(presum,presum[-1]//2+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums=sorted(nums,reverse=True)\n",
    "        i=1\n",
    "        while i<len(nums):\n",
    "            if sum(nums[:i])>sum(nums[i:]):\n",
    "                return nums[:i]\n",
    "            i+=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        left =sum(nums)\n",
    "        sum_res = 0\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "             max_num = nums.pop()\n",
    "             sum_res+=max_num\n",
    "             left-=max_num\n",
    "             res.append(max_num)\n",
    "             if sum_res>left:\n",
    "                 return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        nums.reverse()\n",
    "        a=[]\n",
    "        s=0\n",
    "        i=0\n",
    "        while s <= sum(nums)-s:\n",
    "            a.append(nums[i])\n",
    "            s+=nums[i]\n",
    "            i+=1\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot, s = sum(nums), 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            if s > tot - s:\n",
    "                return nums[:i + 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums_sum = sum(nums)\n",
    "        res = []\n",
    "        sum_ = 0\n",
    "        nums.sort(reverse = True)\n",
    "        for num in nums:\n",
    "            sum_ += num\n",
    "            res.append(num)\n",
    "            if sum_ > (nums_sum-sum_):\n",
    "                return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        prefix = 0\n",
    "        s = sum(nums)\n",
    "        p = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            s -= nums[i]\n",
    "            p += nums[i]\n",
    "            ans.append(nums[i])\n",
    "            if s < p:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        target = sum(nums)//2+1\n",
    "        nums.sort(reverse=True)\n",
    "        cnt = 0\n",
    "        res = []\n",
    "        for i in nums:\n",
    "            cnt += i \n",
    "            res.append(i)\n",
    "            if cnt >= target:\n",
    "                return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        s = sum(nums)\n",
    "        res = []\n",
    "        r = 0\n",
    "        for x in sorted(nums)[::-1]:\n",
    "            r += x\n",
    "            res.append(x)\n",
    "            if r > s - r:\n",
    "                return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse= True)\n",
    "        count=0\n",
    "        index =[]\n",
    "        summ = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            count+=nums[i]\n",
    "            index.append(nums[i])\n",
    "            if summ-count<count:\n",
    "                return index "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        length = len(nums)\n",
    "        nums.append(0)\n",
    "\n",
    "        pos = 1\n",
    "\n",
    "        while pos <= length:\n",
    "            if sum(nums[:pos]) > sum(nums[pos:]):\n",
    "                return nums[:pos]\n",
    "            pos += 1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        # total=sum(nums)\n",
    "        # half=total//2\n",
    "        # list1=[]\n",
    "        # while sum(list1)<=half:\n",
    "        #     a=max(nums)\n",
    "        #     nums.remove(a)\n",
    "        #     list1.append(a)\n",
    "        # return list1\n",
    "        nums.sort(reverse=True)\n",
    "        total=sum(nums)\n",
    "        half=total//2\n",
    "        for i in range(len(nums)+1):\n",
    "            if sum(nums[:i])>half:\n",
    "                return nums[:i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums, reverse = True)  # 将所有数据降序排列\n",
    "        sum_small, sum_big, ans = sum(nums), 0, list()\n",
    "        for i in range(len(nums)):\n",
    "            sum_big += nums[i]\n",
    "            sum_small -= nums[i]\n",
    "            ans.append(nums[i])\n",
    "            if sum_big > sum_small:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        left =sum(nums)\n",
    "        sum_res = 0\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "             max_num = nums.pop()\n",
    "             sum_res+=max_num\n",
    "             left-=max_num\n",
    "             res.append(max_num)\n",
    "             if sum_res>left:\n",
    "                 return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        n = sum(nums) >> 1\n",
    "        big_sum = 0\n",
    "        ans = []\n",
    "        for i in nums:\n",
    "            big_sum += i\n",
    "            ans.append(i)\n",
    "            if big_sum > n:\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        m=len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(m-1,-1,-1):\n",
    "            if sum(nums[:i]) < sum(nums[i:]):\n",
    "                return nums[i:][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        total = sum(nums)\n",
    "        k = total // 2\n",
    "        while sum(ans) <= k:\n",
    "            ans.append(nums.pop())\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        ln, s, t = len(nums), sum(nums), 0\n",
    "        ans = []\n",
    "        for i in range(ln):\n",
    "            ans.append(nums[i])\n",
    "            if sum(ans) > s - sum(ans):\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return nums\n",
    "        else:\n",
    "            sums = sum(nums)\n",
    "            nums.sort(reverse = True)\n",
    "            total = 0\n",
    "            for i in range(len(nums)):\n",
    "                total = total+nums[i]\n",
    "                if total*2>sums:\n",
    "                    return nums[:i+1]\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse = True)  # 将所有数据降序排列\n",
    "        sum_all, sum_big = sum(nums), 0\n",
    "        for i in range(len(nums)):\n",
    "            sum_big += nums[i]\n",
    "            if sum_big > sum_all - sum_big:\n",
    "                return nums[:i + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        total = sum(nums)\n",
    "        k = total // 2\n",
    "        while sum(ans) <= k:\n",
    "            ans.append(nums.pop())\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            m = max(nums)\n",
    "            ans.append(m)\n",
    "            nums.remove(m)\n",
    "            if sum(ans) > sum(nums):\n",
    "                return ans\n",
    "                break\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot, s = sum(nums), 0\n",
    "        for i, num in enumerate(nums):\n",
    "            s += num\n",
    "            if s > tot - s:\n",
    "                return nums[:i + 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        while sum(ans) <= sum(nums):\n",
    "            ans.append(nums[-1])\n",
    "            nums.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "      target = sum(nums)/2\n",
    "      nums.sort(reverse=True)\n",
    "\n",
    "      count = 0\n",
    "      result = []\n",
    "\n",
    "      for x in nums:\n",
    "        count += x\n",
    "        result.append(x)\n",
    "\n",
    "        if count > target:\n",
    "          return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        while(sum(res)<=sum(nums)):\n",
    "            res.append(max(nums))\n",
    "            nums.pop(nums.index(max(nums)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        total=sum(nums)\n",
    "        half=total//2\n",
    "        list1=[]\n",
    "        while sum(list1)<=half:\n",
    "            a=max(nums)\n",
    "            nums.remove(a)\n",
    "            list1.append(a)\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        l = nums.__len__()\n",
    "        if l <= 1:\n",
    "            return nums\n",
    "        nums.sort(reverse=True)\n",
    "        total = sum(nums)\n",
    "        index, cur_sum = 0, 0\n",
    "        while index < l:\n",
    "            cur_sum += nums[index]\n",
    "            if cur_sum > (total - cur_sum):\n",
    "                return nums[:index+1]\n",
    "            index += 1\n",
    "        return []\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        [4, 3, 10, 9, 8],\n",
    "        [4, 4, 7, 6, 7],\n",
    "        [6],\n",
    "    ]:\n",
    "        ret = s.minSubsequence(testcase)\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        h=sum(nums)\n",
    "        ans=0\n",
    "        res=[]\n",
    "        for i in range(len(nums)):\n",
    "            ans+=nums[i]\n",
    "            if ans>h-ans:\n",
    "                return nums[:i+1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        new_num=[0]+list(accumulate(nums))\n",
    "        return nums[:bisect_left(new_num,new_num[-1]//2+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort(reverse=True)\n",
    "        s = sum(nums)\n",
    "        t = 0\n",
    "        for v in nums:\n",
    "            ans.append(v)\n",
    "            t += v\n",
    "            if t > s - t:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        tot,s = sum(nums),0\n",
    "        for i,num in enumerate(nums):\n",
    "            s+=num\n",
    "            if s>tot-s:\n",
    "                return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        num_sum = sum(nums)//2\n",
    "\n",
    "        ans = list()\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            ans.append(nums[i])\n",
    "            num_sum -= nums[i]\n",
    "            if num_sum<0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        length = len(nums)\n",
    "        nums.append(0)\n",
    "\n",
    "        left = nums[0]\n",
    "        right = sum(nums[1:])\n",
    "        cnt = 1\n",
    "\n",
    "        while left <= right:\n",
    "            left += nums[cnt]\n",
    "            right -= nums[cnt]\n",
    "            cnt +=1 \n",
    "        \n",
    "        return nums[:cnt]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        while sum(ans) <= sum(nums):\n",
    "            ans.append(nums[-1])\n",
    "            nums.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums = sorted(nums,key=lambda x:-x)\n",
    "        ans = []\n",
    "        for _ in range(len(nums)):\n",
    "            ans.append(nums.pop(0))\n",
    "            if sum(ans) > sum(nums):\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse = True)\n",
    "        total = sum(nums)\n",
    "        i = 0\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        while cur<= total/2 and i< len(nums):\n",
    "            ans.append(nums[i])\n",
    "            cur+=nums[i]\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        m=len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(m-1,-1,-1):\n",
    "            if sum(nums[:i]) < sum(nums[i:]):\n",
    "                return nums[i:][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse=True)\n",
    "        half = sum(nums) / 2\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s += v\n",
    "            if s > half:\n",
    "                return nums[:i + 1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort(reverse= True)\n",
    "        total,sums = sum(nums),0\n",
    "        for i, num in enumerate(nums):\n",
    "            sums += num\n",
    "            if sums > total - sums:\n",
    "                return nums[:i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if len(set(nums)) == 1:\n",
    "            return nums\n",
    "        nums.sort(reverse=True)\n",
    "        i = 0\n",
    "        while i < n-1:\n",
    "            a = nums[:i+1]\n",
    "            b = nums[i + 1:]\n",
    "            if sum(a) > sum(b):\n",
    "                return nums[:i+1]\n",
    "                break\n",
    "            i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\n",
    "        s=sum(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        ans=[]\n",
    "        t=0\n",
    "        for num in nums:\n",
    "            if t<=s-t:\n",
    "                t+=num\n",
    "                ans.append(num)\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "\n",
    "        # ans = []\n",
    "        # nums.sort()\n",
    "        # while sum(ans) <= sum(nums):\n",
    "        #     ans.append(nums[-1])\n",
    "        #     nums.pop()\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minSubsequence(self, nums: List[int]) -> List[int]:\r\n",
    "        nums.sort(reverse=True)\r\n",
    "        i = 0\r\n",
    "        while i < len(nums):\r\n",
    "            if sum(nums[:i+1]) > sum(nums[i+1:]):\r\n",
    "                return nums[:i+1]\r\n",
    "            else:\r\n",
    "                i += 1\r\n",
    "\r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
